package Solutions;

import java.util.Arrays;
import java.util.List;

/**
 * @Classname SurroundedRegions
 * @Description TODO
 * @Date 2021/6/21 20:31
 * @Created by ASUS
 */
public class SurroundedRegions {
    /***
     * [["X","X","X","X","O","X"],
     * ["O","X","X","O","O","X"],
     * ["X","O","X","O","O","O"],
     * ["X","O","O","O","X","O"],
     * ["O","O","X","X","O","X"],
     * ["X","O","X","O","X","X"]]
     * @param args
     */
    public static void main(String[] args) {
        char[][] test = new char[][]{
                {'X', 'X', 'X', 'X', 'O', 'X'},
                {'O', 'X', 'X', 'O', 'O', 'X'},
                {'X', 'O', 'X', 'O', 'O', 'O'},
                {'X', 'O', 'O', 'O', 'X', 'O'},
                {'O', 'O', 'X', 'X', 'O', 'X'},
                {'X', 'O', 'X', 'O', 'X', 'X'}
        };
        char[][] test1 = new char[][]{
                {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
                {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'O', 'O', 'O', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
                {'X', 'X', 'X', 'X', 'X', 'O', 'O', 'O', 'X', 'O', 'X', 'O', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
                {'X', 'X', 'X', 'X', 'X', 'O', 'X', 'O', 'X', 'O', 'X', 'O', 'O', 'O', 'X', 'X', 'X', 'X', 'X', 'X'},
                {'X', 'X', 'X', 'X', 'X', 'O', 'X', 'O', 'O', 'O', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
                {'X', 'X', 'X', 'X', 'X', 'O', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'}
        };
        new SurroundedRegions().solve(test);
        for (char[] chars : test) {
            for (char aChar : chars) {
                System.out.print(aChar + "\t");
            }
            System.out.println();
        }
    }

    /***
     * 思路:
     *
     * 从边界出发吧，先把边界上和 O 连通点找到, 把这些变成 B,然后遍历整个 board 把 O 变成 X, 把 B 变成 O
     *
     * X	X	X	X	O	X
     * O	X	X	O	O	X
     * X	O	X	O	O	O
     * X	O	O	O	X	O
     * O	O	X	X	O	X
     * X	O	X	O	X	X
     *
     * X	X	X	X	A	X
     * A	X	X	A	A	X
     * X	A	X	A	A	A
     * X	A	A	A	X	A
     * A	A	X	X	O	X
     * X	A	X	A	X	X
     *
     *
     * X	X	X	X	O	X
     * O	X	X	O	O	X
     * X	O	X	O	O	O
     * X	O	O	O	X	O
     * O	O	X	X	X	X
     * X	O	X	O	X	X
     *
     *
     *
     * 执行用时：1 ms, 在所有 Java 提交中击败了99.98% 的用户
     * 内存消耗：40.3 MB, 在所有 Java 提交中击败了83.15% 的用户
     *
     * https://leetcode-cn.com/problems/surrounded-regions/
     */

    public void solve(char[][] board) {
        int m = board.length;
        if (m < 3) return;
        int n = board[0].length;
        if (n < 3) return;

        for (int i = 0; i < n; i++) mark(0, i, board);
        for (int i = 0; i < m; i++) mark(i, n - 1, board);
        for (int i = 0; i < n - 1; i++) mark(m - 1, i, board);
        for (int i = 1; i < m - 1; i++) mark(i, 0, board);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = board[i][j] == 'A' ? 'O' : 'X';
            }
        }

    }

    private void mark(int x, int y, char[][] board) {
        if (x < 0 || x > board.length - 1 || y < 0 || y > board[0].length - 1) return;
        if (board[x][y] == 'O') {
            board[x][y] = 'A';
            mark(x - 1, y, board);
            mark(x + 1, y, board);
            mark(x, y - 1, board);
            mark(x, y + 1, board);
        }
    }
}
